package com.fengye.algorithms.leecode.dp;

/**
 * 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
 *
 * 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
 *
 * 0 <= j <= nums[i] 
 * i + j < n
 * 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/jump-game-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author fengye
 * @Date 2023/5/2 9:34
 **/
public class JumpGameII45 {

    public static void main(String[] args) {
        new JumpGameII45().jump(new int[]{2,3,1,1,4});
    }

    public int jump(int[] nums) {
        int max = 0;
        int end = 0;
        int ans = 0;
        for(int i=0;i<nums.length-1;i++) {
            // 能跳的最远距离
            max = Math.max(max, i+nums[i]);
            // 跳到最远距离了
            if(i == end) {
                end = max;
                ans++;
            }
        }

        return ans;
    }
}
